#define _CRT_SECURE_NO_WARNINGS 1
class Solution {
public:
    bool commpare(int a, int b)
    {
        return a > b;
    }
    int maxArea(vector<int>& height)
    {
        int right = 0, left = height.size() - 1;
        int maxn = 0;
        while (right != left)
        {
            int v = 0;
            int l = left - right;
            if (commpare(height[right], height[left]))
                v = height[left--] * l;
            else
                v = height[right++] * l;
            if (commpare(v, maxn)) maxn = v;
        }
        return maxn;
    }
};
class Solution {
public:
    int Happy(int a)
    {
        int i = 0;
        while (a)
        {
            i += (a % 10) * (a % 10);
            a /= 10;
        }
        return i;
    }
    bool isHappy(int n)
    {
        int fast = Happy(n), slow = n;
        while (fast != slow)
        {
            fast = Happy(Happy(fast));
            slow = Happy(slow);
        }
        if (slow == 1) return true;
        return false;

    }
};
class Solution {
public:
    void duplicateZeros(vector<int>& arr) {
        int dest = -1, cur = 0;
        int n = arr.size() - 1;
        while (cur <= n)
        {
            if (arr[cur]) dest++;
            else dest += 2;
            if (dest >= n) break;
            cur++;
        }
        if (dest > n)
        {
            arr[n] = 0;
            dest -= 2;
            cur--;
        }
        while (cur < dest)
        {
            if (arr[cur]) arr[dest--] = arr[cur--];
            else {
                arr[dest--] = arr[cur];
                arr[dest--] = arr[cur--];
            }
        }
    }
};
class Solution {
public:
    int maxProfit(vector<int>& prices) {
        int low = 1e9, maxn = 0;
        for (auto n : prices)
        {
            low = min(n, low);
            maxn = max(maxn, n - low);
        }
        return maxn;
    }
};
class Solution {
public:
    int removeElement(vector<int>& nums, int val) {
        int left = 0, right = nums.size() - 1;
        while (left <= right)
        {
            if (nums[left] == val)
                swap(nums[left], nums[right--]);
            else left++;
        }
        return left;
    }
};